import java.util.*;

public class PictureCache {
	//Data members
	private LinkedList<Pair> _lru = null; //LRU linked list
	private Map<String, List<String>> _cache = null; //Cache for picture data
	private int _capacity; //Max entries in cache
	
	/**
	 * Constructor
	 * @param capacity - max entries in cache
	 */
	public PictureCache(int capacity) {
		_lru = new LinkedList<Pair>();
		_capacity = capacity;
		_cache = new HashMap<String, List<String>>();
	}
	
	/**
	 * Add new data to cache
	 * @param name - key
	 * @param date - date of current data
	 * @param value - data 
	 */
	public synchronized void add(String name, Date date, List<String> value) {
		
		//Add new data to cache according to its capacity
		if (_lru.contains(name)) {
			_lru.remove(name);
		}
		else if (_lru.size() == _capacity) {
			_cache.remove(_lru.removeLast());
		}
		
		_lru.addFirst(new Pair(name, (Date)date.clone()));
		_cache.put(name, value);
	}
	
	/**
	 * Gets data from cache
	 * @param name - key
	 * @param date - date of validity of data
	 * @return - picture list of fragments
	 */
	public synchronized List<String> getValue(String name, Date date) {
		List<String> result = _cache.get(name);
		
		if (result == null)
			return null;
		
		int index = _lru.indexOf(new Pair(name, null));
		if (index == -1)
			return null;
		
		Pair p = _lru.get(index);
		if (p.getDate().compareTo(date) == -1)
			return null;
		
		return result;
	}	
	
	/**
	 * Key to cache
	 */
	private class Pair {
		//Data members
		private String _name = null; //PicName
		private Date _date = null; //Date of validity
		
		/**
		 * Constructor
		 * @param name - picture name
		 * @param date - validity date
		 */
		public Pair(String name, Date date) {
			_name = name;
			_date = date;
		}
		
		/**
		 * Gets picture name
		 * @return - pic name
		 */
		public String getName() {return _name;}
		
		/**
		 * Gets picture date
		 * @return picture date
		 */
		public Date getDate() {return _date;}
		
		/**
		 * Gets picture date	
		 * @param date
		 */
		public void setDate(Date date) {_date = date;}

		@Override
		public int hashCode() {
			return _name.hashCode();
		}
		
		@Override
		public boolean equals(Object obj) {
			if (!(obj instanceof Pair))
				return false;
			
			Pair other = (Pair)obj;
			
			return _name.equals(other._name);
		}
	}
}
